/*************************************************************************
	> File Name: 003.quick_sort_optimized.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一  9/27 18:50:06 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define max_n 20 

#define swap(a, b) {\
    __typeof(a) _temp = a;\
    a = b;\
    b = _temp;\
}

void quick_sort(int *arr, int left, int right) {
    //1. 针对基准值的优化，「待排序区间」的中间值作为基准值
    //2. 递归改成一半循环，一半递归
    while (left < right) {
        int x = left, y = right, z = arr[(left + right) >> 1];
        do { //左半部分通过循环实现
            while (x <= y && arr[x] < z) x++;
            while (x <= y && arr[y] > z) y--;
            if (x <= y) {
                swap(arr[x], arr[y]);//找到了比基准值小的和比基准值大的，交换这两个值
                x++, y--;
            }
        } while (x <= y);
        quick_sort(arr, x, right);
        right = y;
    }
    return ;
}

int arr[max_n + 5];

void output(int *arr, int n) {
    printf("arr = [");
    for (int i = 0; i < n; i++) {
        printf(" %d", arr[i]);
    }
    printf("]\n");
    return ;
}

int main() {
    srand(time(0));
    for (int i = 0; i < max_n; i++) {
        arr[i] = max_n - i; //完全逆序的数组
    }
    output(arr, max_n);
    long long begin = clock();
    quick_sort(arr, 0, max_n - 1);
    long long end = clock();
    output(arr, max_n);
    printf("(cost %lld ms)\n", (end - begin) * 1000 / CLOCKS_PER_SEC);
    return 0;
}
